\chapter{Liga RoboCup}
\section{Czym jest RoboCup}
\rc{} jest międzynarodową inicjatywą mającą na celu popularyzację i~rozwój robotyki oraz sztucznej inteligencji. Kiedy w 1997 roku powstała liga, twórcy sformułowali następujący cel:
\begin{quote}
Do 2050 roku stworzyć drużynę samodzielnych, humanoidalnych robotów, która wygra z aktualną ludzką drużyną mistrzowską.\cite{robocup}
\end{quote}
Cel ten nadal pozostaje aktualny, jednak wraz z upływem czasu idea \rc{} rozwinęła się i obecnie dzieli się na następujące obszary aktywności:
\begin{description}
\item[RoboCupSoccer] - zajmuje się tworzeniem drużyn autonomicznych robotów grających w piłkę,
\item[RoboCupRescue] - specjalizuje się w budowaniu i oprogramowaniu robotów przeznaczonych do wypełniania zadań związanych z poszukiwaniami oraz ratownictwem w nieprzyjaznym środowisku,
\item[RoboCup@Home] - ma na celu stworzenie robotów współegzystujących z ludźmi i wykonujących zadania w ich naturalnym środowisku,
\item[RoboCupJunior] - popularyzuje robotykę wśród najmłodszych poprzez budowanie i programowanie autonomicznych robotów.
\end{description}

Niewątpliwą zaletą przedsięwzięcia \rc{} jest fakt, iż propaguje ono idee robotyki używając do tego bardzo medialnych środków, a jednocześnie stawiając cele, które są bardzo ambitne i w przyszłości mogą mieć znaczący wpływ na nasze życie. Sama liga jest wymagającym środowiskiem testowym. Roboty działają w dynamicznie zmieniającym się otoczeniu, w którym muszą podejmować decyzje w czasie rzeczywistym w oparciu o ograniczoną liczbę niepewnych danych. Dodatkowo w większości przypadków sterowanie drużyną odbywa się w sposób zdecentralizowany, więc niezbędne stają się mechanizmy koordynacji działań zawodników. Niebagatelną rolę ma także obecność przeciwnika w grze, co dodatkowo motywuje do opracowywania rozwiązań lepszych niż te, którymi dysponuje konkurencyjna drużyna. Tak duża liczba poruszanych zagadnień czyni zadanie stworzenia sprawnie działającej drużyny robotów skomplikowanym i wymagającym.

\section{Historia}

Pierwsze pomysły związane z zastosowaniem robotów grających w gry zespołowe do badań nad robotyką i sztuczną inteligencją sięgają początku lat dziewięćdziesiątych XX wieku. W 1992 roku profesor Alan Mackworth z Uniwersytetu Kolumbii Brytyjskiej w Kanadzie po raz pierwszy wspomniał o tego typu eksperymentach w pracy \w{On Seeing Robots} \cite{dynamo}. Jego grupa stosowała zmodyfikowane zdalnie sterowane zabawki do gry w piłkę nożną w ramach projektu \w{Dynamo}. Głównym celem były badania nad sposobami zbierana danych o otoczeniu. Początkowo roboty te były wyposażone w znaczniki, a informacje o ich położeniu pochodziły z kamery zainstalowanej nad boiskiem, w późniejszych pracach sensory zostały zintegrowane z~konstrukcjami robotów (por. rys. \ref{fig:dynamo}).

	\begin{figure}[b]
	\centering
	\includegraphics[scale=0.45]{./dynamo}
	\caption{ Zawodnik strzelający na bramkę, projekt \w{Dynamo} \newline
	(źródło: \cite{dynamo}) } \label{fig:dynamo}
	\end{figure}

W tym samym roku naukowcy biorący udział w konferencji \w{Grand Challenges in Artifical Intelligence} odbywających się w Tokio doszli do wniosku, że roboty grające w piłkę nożna będą idealnym sposobem na promocję nauki i techniki w nadchodzących latach. Inicjatywa spotkała się z aprobatą i~w~1993~roku powstała pierwsza japońska liga robotów \w{J-League}, która szybko przykuła uwagę zagranicznych ośrodków naukowych. Po nawiązaniu współpracy \w{J-League} przemianowano na \w{RoboCup} (skrót od \w{Robot World Cup Initiative}). Początek przedsięwzięcia ogłoszono oficjalnie we wrześniu 1993 roku, wtedy też rozpoczęto opracowywanie zasad gry. W międzyczasie zespół badaczy pracujący w japońskim rządowym ośrodku naukowym \w{ElectroTechnical Laboratory} (ETL) podjął prace nad stworzeniem symulatora rozgrywek piłkarskich, który z czasem stał się oficjalnym symulatorem stosowanym w \rc{}.

	\begin{figure}[!b]
	\centering
	\includegraphics[scale=0.5]{./2010_singapore}
	\caption{ \w{Robocup 2010}, Singapur\\
	(źródło: \protect\url{www.robocup2010.org}) } \label{fig:2010_singapore}
	\end{figure}

Prace nad ligą okazały się złożonym przedsięwzięciem. W 1996 roku udało się rozegrać zawody \w{Pre-RoboCup-96}, podczas których odbyły się rozgrywki symulacyjne oraz zaprezentowano prototypowe konstrukcje robotów. Pierwsze pełne rozgrywki ligi \rc{} odbyły się rok później w Japonii. Brało w nich udział ponad 40 drużyn (symulacyjnych oraz dysponujących fizycznymi konstrukcjami robotów), a oglądało ponad 5000 widzów. Zawody okazały się sporym sukcesem i dały ludziom zaangażowanym w \rc{} motywację do dalszych prac. 

Obecnie oprócz ogólnoświatowych zawodów corocznie odbywają się także lokalne turnieje, takie jak \w{RoboCup Iran Open 2011} czy \w{RoboCup Germany Open 2011}. Ranga ligi rośnie z roku na rok, co potwierdzają statystyki: w 2010 roku w Singapurze w rozgrywkach brało udział aż 500 drużyn z 40 krajów.

\section{Podział na ligi robotów}

Liga \rc{} (a dokładnie \w{RoboCupSoccer}) jest podzielona na pięć lig, różniących się zasadami, dozwolonymi konstrukcjami robotów, wyglądem boiska oraz sposobami komunikacji między zawodnikami. Poniżej przedstawiono krótką charakterystykę każdej z nich.

\subsection{Liga symulacyjna}

	\begin{figure}[!b]
	\centering
	\subfloat[Symulator 2d]{\includegraphics[scale=0.18]{./2d_sim}}
	\hspace{0.5cm}
	\subfloat[Symulator 3d]{\includegraphics[scale=0.435]{./3d_sim}}
	\caption{Liga symulacyjna\\
	(źródło: \protect\url{www.robocup2011.org})} 
	\label{fig:liga_symulacyjna}
	\end{figure}

Jest to najstarsza z lig. Jej głównym celem jest skupienie się na rozwoju algorytmów sztucznej inteligencji oraz współpracy zawodników. Rozgrywki odbywają się w dwóch rodzajach symulatorów: dwu- oraz trójwymiarowym (od 2006 roku). Symulacja dwuwymiarowa to mecze dwóch drużyn po 11 zawodników na pełnowymiarowym boisku zgodnym z regułami FIFA. Za~sterowanie każdym z zawodników odpowiada niezależny program podłączony do aplikacji \w{SoccerServer}, której rolą jest symulacja gry. Każdy z graczy otrzymuje od serwera porcję danych stanowiącą wejście jego wirtualnych sensorów. W oparciu o te dane jest w stanie wpływać na środowisku wykonując elementarne akcje, takie jak przemieszczanie się i kopanie. Symulacja zjawisk fizycznych jest ograniczona do minimum, co pozwala twórcom oprogramowania skupić się na algorytmach związanych z rozgrywką.

Inaczej jest w przypadku symulacji trójwymiarowej. Jest ona oparta na symulatorze \w{SimSpark}. Jego twórcy postawili na wierne odwzorowanie cech fizycznych robotów. Początkowo dla uproszczenia posługiwano się tylko sferycznym modelem zawodnika. Od 2006 roku za oficjalny model służył humanoidalny robot \w{Fujitsu HOAP-2}. W 2008 roku zdecydowano się zmienić go na używany do dziś model robota \w{Nao} firmy \w{Aldebaran Robotics}. Roboty takie są stosowane także w lidze platformy standardowej (opisanej w sekcji~\ref{sec:SPL}), więc liga symulacyjna pozwala w tym przypadku przetestować niektóre rozwiązania przed zastosowaniem ich na prawdziwych robotach. Obecnie głównym problemem, na którym skupia się działalność ligi trójwymiarowej, jest opracowanie niezawodnego sterowania dla robota humanoidalnego (zapewnienie sprawnego poruszania się po planszy, utrzymanie równowagi, kontrola nad piłką itd.). Jednak wraz z postępem prac naukowcy liczą na to, że w przyszłości będą mogli się skupić na oprogramowaniu bardziej złożonych zachowań związanych z grą zespołową.


\subsection{Liga małych robotów}

	\begin{figure}[!b]
	\centering
	\includegraphics[width=0.6\textwidth]{./ssl}
	\caption{Zawodnicy w lidze małych robotów \\
	(źródło: \protect\url{http://avaxnews.com/appealing/RoboCup.html})} 
	\end{figure}

Jest to pierwsza z lig (zwana także ligą F180), w której grają fizyczne roboty. Gra odbywa się na boisku o powierzchni ok. $25~m^{2}$. W rozgrywce biorą udział dwie drużyny. Każda składa się z pięciu cylindrycznych robotów wyposażonych w kołową bazę jezdną. Zawodnicy nie posiadają sensorów, dane o ich położeniu oraz o otoczeniu pochodzą z kamery umieszczonej nad boiskiem. Rozgrywki w tej lidze są bezpośrednio związane z tematem niniejszej pracy, dlatego też opisano ją szczegółowo w paragrafie~\ref{sec:f180}.


\subsection{Liga średnich robotów}

W tej lidze w skład każdej z drużyn wchodzi sześciu zawodników. Rozgrywki odbywają się zgodnie z regułami FIFA (w których dokonano drobnych modyfikacji), przy użyciu standardowej piłki. Mecze rozgrywane są na boisku o wymiarach $18\times12$ metrów. Fizyczne wymiary robotów są ograniczone do cylindra o średnicy $50~cm$, a masa zawodnika nie może przekroczyć $40~kg$. W odróżnieniu od ligi \w{Small Size}, roboty są tutaj w pełni autonomiczne - są wyposażone w zestaw sensorów oraz komputer pełniący rolę kontrolera. Oprócz tego mają one możliwość bezprzewodowej komunikacji między sobą, co poprawia zdolności współpracy w grze drużynowej, a także pozwala na odbieranie decyzji sędziego. Poza dokonywaniem ewentualnych zmian zawodników, ludzie w żaden sposób nie interweniują podczas gry. 

	\begin{figure}[!b]
\vspace{1cm}
	\centering
	\includegraphics[width=0.8\textwidth]{./msl}
	\caption{Rozgrywki ligi średnich robotów \\
	(źródło: \protect\url{http://www.robocup2011.org})} 
	\end{figure}

Z roku na rok dokonywane są drobne modyfikacje w regulaminie rozgrywek. Przykładowo w 2010 roku bramki były oznaczane kolorami, dzięki czemu roboty rozpoznawały bramkę swoją oraz przeciwnika. W 2011 roku markery usunięto i zawodnicy musieli poradzić sobie z rozpoznawaniem bramek identycznych z tymi stosowanymi w rozgrywkach FIFA. Tego rodzaju zmiany pozwalają na zapewnienie ciągłego rozwoju ligi przez stawianie nowych wyzwań twórcom robotów.

\subsection{Liga platformy standardowej \label{sec:SPL}}
	\begin{wrapfigure}{r}{0.52\textwidth}
	\centering
	\includegraphics[width=0.50\textwidth]{./nao_game}
	\caption{Roboty \w{Nao} podczas gry \\
	(źródło: \protect\url{http://www.ist.tugraz.at})} 
	\end{wrapfigure}
Podstawową cechą, która wyróżnia tę ligę, jest fakt, iż wszystkie drużyny biorące w niej udział używają ustandaryzowanej konstrukcji robota. Początkowo były to czworonożne ,,pieski'' \w{Sony AIBO}, które w 2008 roku zastąpiono humanoidalnymi robotami \w{NAO} firmy \w{Aldebaran Robotics}. Roboty te są bardzo bogato wyposażone: posiadają solidną bazę czujników (2 kamery CMOS, 4 mikrofony, żyroskop, akcelerometr, 4 sonary ultradźwiękowe) i oprogramowania multimedialnego: moduł rozpoznawania mowy, twarzy, kształtów oraz wiele innych. Ich konstrukcja posiada aż 21 stopni swobody. Tak dopracowana platforma pozwala naukowcom skupić się na rozwoju zaawansowanego oprogramowania.

Mecze odbywają się zgodnie z regułami FIFA na boisku o wymiarach $7.4\times5.4~m$. W rozgrywkach stosowana jest pomarańczowa piłka do hokeja ulicznego, a bramki są oznaczone odpowiednio żółtym oraz niebieskim kolorem. Drużyny składają się z trzech zawodników oraz bramkarza. Roboty są w pełni autonomiczne, ale mogą porozumiewać się ze sobą za pomocą komend dźwiękowych oraz po sieci WiFi. Grę nadzoruje trzech sędziów. Rozgrywki są dość widowiskowe, ale pokazują także, że zawodnikom \w{NAO} dużo jeszcze brakuje do ich ludzkich przeciwników.

\subsection{Liga robotów humanoidalnych}

	\begin{figure}[!b]
	\centering
	\includegraphics[width=0.8\textwidth]{./humanoid}
	\caption{Roboty humanoidalne podczas gry\\
	(źródło: \protect\url{http://www.vt.edu})} 
	\end{figure}

Celem tej ligi jest stworzenie konstrukcji robotów jak najbardziej przypominających człowieka. Dozwolone są tylko takie sensory, które odpowiadają ludzkim zmysłom. Muszą być także rozmieszczone w podobny sposób. Unika się więc takich ułatwień, na jakie mogą sobie pozwolić zespoły tworzące oprogramowanie w lidze platformy standardowej, gdzie dostępne są np. dane z czujników odległości. Oprócz problemu poprawnej percepcji i modelowania otoczenia, liga dostarcza także innych wyzwań technicznych. Rozwiązanie takich problemów, jak sprawne chodzenie czy bieganie robotów lub kopanie piłki jest ciągle w obszarze badań.

Liga jest podzielona na trzy klasy. Kryterium stanowią tutaj rozmiary robota. Mamy zatem zawody \w{KidSize} (roboty o rozmiarach $30-60~cm$), \w{TeenSize} ($100-120~cm$) oraz \w{AdultSize} (powyżej $130~cm$). W przypadku \w{KidSize} drużyny składają się z trzech robotów. W kategorii \w{TeenSize} zmagają się po 2 roboty, natomiast rozgrywka w \w{AdultSize} polega na naprzemiennym oddawaniu strzałów na bramkę przeciwnika (mamy więc po jednym robocie w każdej drużynie). 

Podstawowym zadaniem ligi humanoidalnej na najbliższe lata jest doskonalenie konstrukcji mechanicznych zawodników. Wraz ze zwiększaniem się umiejętności robotów możliwa będzie implementacja zaawansowanych algorytmów gry zespołowej.

\section{Charakterystyka ligi małych robotów\label{sec:f180}}

Rozgrywki ligi małych robotów należą do bardzo widowiskowych. Zawodnicy mają spore możliwości techniczne, przez co mecze wyglądają naprawdę ciekawie. Dużą zaletą jest stosunkowo prosta konstrukcja robotów, co otwiera drzwi do \rc{} mniej zasobnym zespołom. Także na Wydziale Elektroniki i Technik Informacyjnych Politechniki Warszawskiej od lat prowadzone są działania, które mają na celu stworzenie kompletnej drużyny robotów \w{Small Size}. Również autor tej pracy ma nadzieję mieć swój wkład w tę działalność. Z tego względu zdecydowano się na szczegółowy opis ligi, aby dobrze przybliżyć specyfikę jej rozgrywek. Jest on oparty na aktualnym regulaminie dostępnym na oficjalnej stronie internetowej \cite{small_size}.

W meczach ligi \w{Small Size} biorą udział dwie drużyny składające się z maksymalnie pięciu robotów, przy czym jednemu z nich można przed meczem przydzielić rolę bramkarza. Konstrukcja zawodników musi mieścić się w cylindrze o średnicy $18~cm$ i wysokości $15~cm$. Roboty grają używając pomarańczowej piłki do golfa na pokrytym zielonym dywanem boisku o wymiarach $4.05\times6.05~m$. 

Stan gry obserwowany jest przez umieszczone nad boiskiem dwie kamery systemu wizyjnego. Zarejestrowany obraz trafia do programu \w{SSL-Vision}\footnote{Jest to otwarte oprogramowanie utrzymywane przez społeczność ligi, dostępne pod adresem \url{http://code.google.com/p/ssl-vision/}}, który przetwarza go tworząc ustandaryzowany opis sytuacji na boisku. Zawierają on dane o położeniach i prędkościach poszczególnych robotów oraz piłki. Informacja ta jest transmitowana do stojących poza boiskiem komputerów, na których uruchomione jest oprogramowanie sterujące drużynami. Na podstawie aktualnej sytuacji w grze oblicza ono odpowiednie wartości sterowań, które są zadawane robotom drogą radiową. W ten sam sposób przekazuje się także komendy sędziego (używana jest do tego aplikacja \w{SSL Referee Box}\footnote{\url{http://small-size.informatik.uni-bremen.de/referee:download}}).

	\begin{figure}[!t]
	\centering
	\includegraphics[width=0.6\textwidth]{./komunikacja}
	\caption{Przepływ komunikacji w lidze \w{Small Size}} 
	\end{figure}

	\begin{figure}[!b]
	\centering
	\includegraphics[width=0.4\textwidth]{./dribbler}
	\caption{\label{fig:dribbler}Zasada działania \w{dribblera}} 
	\end{figure}

Konstrukcje robotów oparte są na omnikierunkowej bazie jezdnej. Daje ona możliwość swobodnego poruszania się po boisku (prędkości zawodników dochodzą nawet do $5~m/s$) i jednocześnie utrzymywania zadanej rotacji. Zawodnicy są wyposażeni w specjalne narzędzie zwane \w{dribblerem} (por.~rys.~\ref{fig:dribbler}). Pozwala ono nadać piłce rotację wsteczną, dzięki czemu robot może np. wykonywać obroty lub zatrzymywać się nie tracą nad nią kontroli. Możliwości dryblingu są jednak ograniczone regulaminem - robot może pokonać z piłką maksymalnie $50~cm$ (zasada ta ma za zadanie promować grę zespołową). Do kopania piłki roboty używają \w{kickera} - jest to specjalny element konstrukcji zawodnika, który nie tylko pozwala na podawanie czy oddawanie strzałów, ale także na podrzucanie piłki. Maksymalna prędkość, z jaką robot może strzelać, jest ograniczona do $10~m/s$. 

Fakt, iż roboty nie posiadają sensorów wizyjnych, a całość rozgrywki obserwowana jest przez kamery nad boiskiem, narzuca dodatkowe ograniczenia. Konstrukcja zawodnika nie może przysłaniać więcej niż 20\% powierzchni piłki - jest to niezbędne do poprawnego rozpoznania jej pozycji przez oprogramowanie \w{SSL-Vision}. Z tego samego powodu każdy z robotów musi być wyposażony w unikatowy kolorowy znacznik, który umożliwia jego jednoznaczną identyfikację na boisku. Znacznik ten musi być umieszczony na górze robota i widoczny dla kamery. Kolor elementów znacznika określa zarówno przynależność do drużyny, jak i numer konkretnego zawodnika. Przykładowe znaczniki przedstawia rys.~\ref{fig:znaczniki}.
	\vspace{2cm}
	\begin{figure}[!h]
	\centering
	\includegraphics[width=0.6\textwidth]{./znaczniki}
	\caption{\label{fig:znaczniki}Przykładowe znaczniki umieszczane na robotach} 
	\end{figure}
